package com.beck.bee.sort;

/**
 * Created by cdliubei@jd.com on 4/13/2017.
 */
public class MergeSort {

    void mergeArray(int a[], int first, int mid, int last, int temp[])
    {
        int i = first, j = mid + 1;
        int m = mid,   n = last;
        int k = 0;

        while (i <= m && j <= n)
        {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }

        while (i <= m)
            temp[k++] = a[i++];

        while (j <= n)
            temp[k++] = a[j++];

        for (i = 0; i < k; i++)
            a[first + i] = temp[i];
    }

    public void mergeSort(int[] array){
        if (null == array || array.length < 1) {
            return;
        }
        doMergeSort(array,0,array.length-1,new int[array.length]);
        for (int val : array){
            System.out.print(val + " ");
        }
    }

    void doMergeSort(int[] array, int low, int high, int[] temp){
        int mid = (low + high) / 2;
        if (low < high){
            doMergeSort(array,low,mid,temp);
            doMergeSort(array,mid+1,high,temp);
            mergeArray(array,low,mid,high,temp);
        }else {
            return;
        }
    }

    public static void main(String[] args) {
        int[] a = { 3, 7, 2, 4, 10, 9, 12, 5 };
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(a);

    }
}
